package com.zhaofan.other;

import org.junit.Test;

import java.awt.image.renderable.RenderableImage;
import java.util.LinkedList;

/**
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 中心扩散法
 */
public class No5 {
    @Test
    public void test() {
        String s = "babad";
        System.out.println(longestPalindrome(s));
//        System.out.println("1234567".substring(0,7));
    }

    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) return s;

        int len = 0;
        String str = "";
        for (int i = 1; i < s.length(); ++i) {
            char c = s.charAt(i);
            int left = i - 1, right = i + 1, curLen = 1;
            while (left >= 0 && s.charAt(left) == c) {
                left--;
                ++curLen;
            }

            while (right < s.length() && s.charAt(right) == c) {
                right++;
                ++curLen;
            }

            while (left >= 0 &&right < s.length() &&s.charAt(left)==s.charAt(right)) {
                ++right;
                --left;
                curLen+=2;
            }

            if(str.length()<curLen){
                str=s.substring(left+1, right);
            }
        }
        return str;
    }
}


